class Walk;


class Sym {
  int DIM;
 public:
  int * perm;
  int * sign;
  Sym(int d);
  ~Sym();
  void print();
  void act_on_pos(int * pos);
  void act_on_walk(Walk&);
};

class perm_list {
    int DIM;
    int counter;
    int ** list;
    void add_perm(int * perm);
    void make_list();
    void recursive(int * perm, int level);
 public:
    void shift_perm(int *perm,int n);
    int factorial(int);
    void print();
    void get(int * perm, int n);
    perm_list() {}
    void init(int d);
    ~perm_list();
};
  
class signs {
  int DIM;
  int counter;
  int ** list;
  void add_line(int * line);
  void recursive(int * line, int level);
  void make_list();
 public:
  void get(int * line,int n);
  signs() {}
  void init(int d);
  signs(int d);
  ~signs();
  void print();
};

class Sym_group{
  int DIM,N_sym;
  perm_list plist;
  signs slist;
 public:
  Sym_group(int d);
  void get(Sym& sym1,int n);
  int get_size();
  bool pivot(Walk&,Table&);
};

int perm_list::factorial(int n) {
  if (n==1) return 1;
  else return n*factorial(n-1);
}


void perm_list::init(int d) {
  int i;
  counter=0;
  DIM=d;
  list = new int*[factorial(DIM)];
  for (i=0;i<factorial(DIM);i++) {
    list[i]=new int[DIM];
  }
  make_list();
}

perm_list::~perm_list() {
  int i;
  for (i=0;i<factorial(DIM);i++) {
    delete [] list[i];
  }
  delete [] list;
}

void perm_list::get(int * perm,int n) {
  int i;
  for (i=0;i<DIM;i++) {
    perm[i]=list[n][i];
  }
}

void perm_list::shift_perm(int * perm,int n) {
  int i,x;
  x=perm[DIM-1];
  for (i=DIM-1;i>n;i--) {
    perm[i]=perm[i-1];
  }
  perm[n]=x;
}

void perm_list::add_perm(int * perm) {
  int i;
  for (i=0;i<DIM;i++) {
    list[counter][i]=perm[i];
  }
  counter++;
}

void perm_list::make_list() {
  int i;
  int * perm;
  perm= new int[DIM];
  for (i=0;i<DIM;i++) {
    perm[i]=i;
  }
  recursive(perm,DIM-1);
  delete [] perm;
}

void perm_list::recursive(int * perm, int level) {
  int i;
  if (level==0) {
    add_perm(perm);
  }
  else {
    int * perm2;
    perm2=new int[DIM];
    for (i=0;i<DIM;i++) {
    perm2[i]=perm[i];
    }
    recursive(perm2,level-1);
    for (i=0;i<level;i++) {
      shift_perm(perm2,DIM-1-level);
      recursive(perm2,level-1);
    }
    delete [] perm2;
  }
}
    
void perm_list::print() {
  int i,j;
  cout << "\n";
  for (i=0;i<factorial(DIM);i++) {
    for (j=0;j<DIM;j++) {
      cout << list[i][j] << "\t";
    }
    cout << "\n";
  }
}

signs::signs(int d) {
  int i;
  counter=0;
  DIM=d;
  int length=pow(2,DIM);
  list = new int*[length];
  for (i=0;i<pow(2,DIM);i++) {
    list[i]=new int[DIM];
  }
  make_list();
}

void signs::init(int d) {
  int i;
  counter=0;
  DIM=d;
  int length=pow(2,DIM);
  list = new int*[length];
  for (i=0;i<pow(2,DIM);i++) {
    list[i]=new int[DIM];
  }
  make_list();
}

signs::~signs() {
  int i;
  for (i=0;i<pow(2,DIM);i++) {
    delete [] list[i];
  }
  delete [] list;
}


void signs::get(int * line,int n) {
  int i;
  for (i=0;i<DIM;i++) {
    line[i]=list[n][i];
  }
}

void signs::add_line(int *line) {
  int i;
  for (i=0;i<DIM;i++) {
    list[counter][i]=line[i];
  }
  counter++;
}

void signs::make_list() {
  int i;
  int * line;
  line=new int[DIM];
  recursive(line,0);
  delete [] line;
}

void signs::recursive(int * line,int level) {
  int i;
  if (level==DIM) add_line(line);
  else {
    for (i=0;i<2;i++) {
      line[level]=i;
      recursive(line,level+1);
    }
  }
}

void signs::print() {
  int i,j;
  cout << "\n";
  for (i=0;i<pow(2,DIM);i++) {
    for (j=0;j<DIM;j++) {
      cout << list[i][j] << "\t";
    }
    cout << "\n";
  }
}

Sym_group::Sym_group(int d) {
  plist.init(d);
  slist.init(d);
  //cout<< "permutations:\n";
  //plist.print();
  //cout << "signs:\n";
  //slist.print();
  DIM=d;
  N_sym=pow(2,DIM)*plist.factorial(DIM);
}

void Sym_group::get(Sym& sym1,int n) {
  int n1; 
  int n2;
  int N=pow(2,DIM);
  n2 = n % N;
  n1 = n / N;
  plist.get(sym1.perm,n1);
  slist.get(sym1.sign,n2);
}

int Sym_group::get_size() {
  return N_sym;
}

Sym::Sym(int d) {
  DIM=d;
  perm = new int[d];
  sign = new int[d];
}

Sym::~Sym() {
  delete [] perm;
  delete [] sign;
}

void Sym::print() {
  int i;
  cout << "permutation: ";
  for (i=0;i<DIM;i++) {
    cout << perm[i];
  }
  cout <<"\nsigns: ";
  for (i=0;i<DIM;i++) {
    cout << sign[i];
  }
  cout << "\n";
}

void Sym::act_on_pos(int * pos) {
  int i;
  int * pos1;
  pos1 = new int[DIM];
  for (i=0;i<DIM;i++) {
    pos1[i]=pos[perm[i]]*pow(-1,sign[i]);
  }
  for (i=0;i<DIM;i++) {
    pos[i]=pos1[i];
  }
  delete [] pos1;
}

void Sym::act_on_walk(Walk& walk1) {
  int i,j,step;
  int * pos1;
  int * pos2;
  int * diff;
  int N=walk1.get_length();
  pos1=new int[DIM];
  pos2=new int[DIM];
  diff=new int[DIM];
  walk1.get_pos(0,pos1);
  for (i=0;i<N;i++) {
    walk1.get_pos(i+1,pos2);
    act_on_pos(pos2);
    walk1.set_pos(i+1,pos2);
    for (j=0;j<DIM;j++) {
      diff[j]=pos2[j]-pos1[j];
      if (diff[j]!=0) step=j*2+1;
      if (diff[j]==-1) step++;
    }
    walk1.set_step(i,step);
    walk1.get_pos(i+1,pos1);
  }
  walk1.set_R_EE();
  delete [] pos1;
  delete [] pos2;
  delete [] diff;
}

bool Sym_group::pivot(Walk& walk,Table& table1) {
  int s,i,N;
  int * pos;
  float r;
  Sym sym1(DIM);
  N=walk.get_length();
  pos= new int[DIM];
  for (i=0;i<DIM;i++) {
    pos[i]=0;
  }
  s=ran2_int(&idum,0,N_sym-1);;
  get(sym1,s);
  //cout<< "symmetry:\n";
  sym1.print();
  s=ran2_int(&idum,0,N-1);
  //cout << "position: " << s << "\n";
  Walk walk1(s,DIM);
  Walk walk2(N-s,DIM);
  Walk walk3(N,DIM);
  walk.split_walk(walk1,walk2);
  walk2.set_start(pos);
  sym1.act_on_walk(walk2);
  walk3.add_walks(walk1,walk2);
  delete [] pos;
  if (walk3.check_SA(table1)==1) {
    walk.add_walks(walk1,walk2);
    walk.set_R_EE();
    return 1;
  }
  else return 0;
}    
    
